#include "../tools.h"

void merge_arr(vector<int>& arr, int left, int m, int right, vector<int>& tmp);
void merge_sort(vector<int>& vec, int left, int right, vector<int>& tmp);

int main(int argc, char const *argv[])
{
    vector<int> data = {6, 2, 1, 7, 9, 2, 4, 5, 10, 8};
    vector<int> tmp(data.size(), 0);

    merge_sort(data, 0, data.size() - 1, tmp);
    show(data);

    return 0;
}

void merge_arr(vector<int>& arr, int left, int m, int right, vector<int>& tmp){
    int l_end = m, r_end = right;
    int p = left, p_l = left, p_r = m + 1;
    while(p_l <= l_end && p_r <= r_end){
        if(arr[p_l] < arr[p_r]) tmp[p++] = arr[p_l++];
        else tmp[p++] = arr[p_r++];
    }
    while(p_l <= l_end) tmp[p++] = arr[p_l++];
    while(p_r <= r_end) tmp[p++] = arr[p_r++];
    for(int i = left; i <= right; ++i)
        arr[i] = tmp[i];
}

// 二叉拆分，后序遍历
void merge_sort(vector<int>& vec, int left, int right, vector<int>& tmp){
    if(left >= right) return;

    int m = (left + right) / 2;
    merge_sort(vec, left, m, tmp);
    merge_sort(vec, m + 1, right, tmp);

    merge_arr(vec, left, m, right, tmp);
}